Number of music playlists¶
Time: O(NxL); Space: O(L); hard
Your music player contains N different songs and she wants to listen to L (not necessarily different) songs during your trip. You create a playlist so that:
Every song is played at least once
A song can only be played again only if K other songs have been played
Return the number of possible playlists. As the answer can be very large, return it modulo 10^9 + 7.
Example 1:
Input: N = 3, L = 3, K = 1
Output: 6
Explanation:
There are 6 possible playlists:
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
Example 2:
Input: N = 2, L = 3, K = 0
Output: 6
Explanation:
There are 6 possible playlists:
[1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2]
Example 3:
Input: N = 2, L = 3, K = 1
Output: 2
Explanation:
There are 2 possible playlists:
[1, 2, 1], [2, 1, 2]
Constraints:
0 <= K < N <= L <= 100
1. Dynamic Programming [O(NxL), O(NxL)]¶
Intuition
Let dp[i][j] be the number of playlists of length i that have exactly j unique songs. We want dp[L][N], and it seems likely we can develop a recurrence for dp.
Algorithm
Consider dp[i][j]. Last song, we either played a song for the first time or we didn’t. If we did, then we had dp[i-1][j-1] * (N-j) ways to choose it. If we didn’t, then we repeated a previous song in dp[i-1][j] * max(j-K, 0) ways (j of them, except the last K ones played are banned.)
[3]:
from functools import lru_cache
class Solution1(object):
"""
Time: O(N*L)
Space: O(N*L). (However, we can adapt this algorithm to only store the last row of dp to easily get O(L) space complexity.)
"""
def numMusicPlaylists(self, N, L, K):
"""
:type N: int
:type L: int
:type K: int
:rtype: int
"""
MOD = 10**9+7
@lru_cache(None)
def dp(i, j):
if i == 0:
return +(j == 0)
ans = dp(i-1, j-1) * (N-j+1)
ans += dp(i-1, j) * max(j-K, 0)
return ans % MOD
return dp(L, N)
[4]:
s = Solution1()
N = 3
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 0
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 2
2. Dynamic Programming [O(NxL), O(L)]¶
[5]:
class Solution2(object):
"""
Time: O(N*L)
Space: O(L)
"""
def numMusicPlaylists(self, N, L, K):
"""
:type N: int
:type L: int
:type K: int
:rtype: int
"""
MOD = 10**9+7
dp = [[0 for _ in range(1+L)] for _ in range(2)]
dp[0][0] = dp[1][1] = 1
for n in range(1, N+1):
dp[n % 2][n] = (dp[(n-1) % 2][n-1] * n) % MOD
for l in range(n+1, L+1):
dp[n % 2][l] = ((dp[n % 2][l-1] * max(n-K, 0)) % MOD +
(dp[(n-1) % 2][l-1] * n) % MOD) % MOD
return dp[N % 2][L]
[6]:
s = Solution2()
N = 3
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 0
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 2
3. Partitions + Dynamic Programming [O(NxL), O(L)]¶
[7]:
class Solution3(object):
"""
Time: O(N*L)
Space: O(L)
"""
def numMusicPlaylists(self, N, L, K):
MOD = 10**9 + 7
# dp[S] at time P = <S, P> as discussed in article
dp = [1] * (L-N+1)
for p in range(2, N-K+1):
for i in range(1, L-N+1):
dp[i] += dp[i-1] * p
# Multiply by N!
ans = dp[-1]
for k in range(2, N+1):
ans *= k
return ans % MOD
[8]:
s = Solution3()
N = 3
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 0
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 2
4. Generating Functions [O(NLogL), O(1)]¶
[9]:
class Solution4(object):
"""
Time: O(NLogL)
Space: O(1)
"""
def numMusicPlaylists(self, N, L, K):
MOD = 10**9 + 7
def inv(x):
return pow(x, MOD-2, MOD)
C = 1
for x in range(1, N-K):
C *= -x
C %= MOD
C = inv(C)
ans = 0
for k in range(1, N-K+1):
ans += pow(k, L-K-1, MOD) * C
C = C * (k - (N-K)) % MOD * inv(k) % MOD
for k in range(1, N+1):
ans = ans * k % MOD
return ans
[10]:
s = Solution4()
N = 3
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 0
assert s.numMusicPlaylists(N, L, K) == 6
N = 2
L = 3
K = 1
assert s.numMusicPlaylists(N, L, K) == 2